package algorithm.leetcode.I201to400;

/**
 * 这题直接背答案吧,下面大佬总结的规律
 *
 * 如果是偶数,直接右移
 * 如果是奇数,分两种情况
 *     如果末尾是...11,就+1
 *     如果末尾是...01,就-1
 *     例外是 3 (11),这个先-1再右移,步骤数为2,如果先+1再右移步骤数为3
 *
 * trick: n可能是int上限,+1会溢出,需要转化为long
 */

public class Q397 {

    public int integerReplacement(int n) {
        int operations = 0;
        long m = n;
        while (m > 1) {
            if ((m & 1) == 0) m >>= 1;
            else {
                if (m == 3) m--;
                else if ((m & 3) == 3) m++;
                else m--;
            }
            operations++;
        }
        return operations;
    }

    public static void main(String[] args) {
        Q397 q397 = new Q397();
        System.out.println(q397.integerReplacement(10000));
    }

}
